This invention is related to a method of scheduling computer storage input and output requests to provide minimum quality of service guarantees.
Increasingly, computer users are relying upon a single computing platform to execute multiple applications. In such situations, the various applications executing on the platform must share access to the available system resources, such as disk I/O. In those situations where available resources far exceed the requirements of the applications, control of access to system resources can be relatively straightforward. However, it is often not practical or economical to over provision resources in this manner. Thus, the operating system must make various resource allocation decisions for the various executing processes.
In many situations, it is desirable for a process to be provided with a guaranteed minimum level of system resources. For example, multimedia applications often require that I/O services (e.g., disk or network accesses) be provided with a certain quality of service (e.g., minimum throughput or maximum delay). If the quality of service declines, the performance of the application can suffer, resulting in jerky video display, choppy audio, and other problems.
Ideally, a system should provide a quality of service (xe2x80x9cQoSxe2x80x9d) guarantee to an application requesting it. If the minimum performance requirement for the requested service cannot be guaranteed, the system should not accept the request.
Conventional operating systems, such as Windows NT and UNIX both dynamically compute the priorities of unprivileged processes and allocate system resources accordingly. Although high priority applications are serviced in advance of lower priority applications, such systems do not guarantee minimum service levels. While a user may be merely annoyed of the system delays the execution of an interactive application to service another process, such a delay in a multimedia application can render the application""s audio or video output wholly unusable.
A variety of specific scheduling algorithms have been proposed to provide levels of QoS guarantees. However, these conventional approaches consider each resource in isolation, neglecting interactions. Unfortunately, this is not realistic due to xe2x80x9cclosed-loopxe2x80x9d nature of most applications: After completion of a request on one resource (e.g., disk), applications often have to compete for another resource (e.g., CPU) before being able to make another request on the first resource. In such situations, scheduling delays on each resource can accumulate and make actual throughput much lower than expected if each resource is considered in isolation.
A disk scheduling algorithm with high cumulative service guarantees, low delay, and good fairness is provided by assigning I/O requests from various system elements to particular domains. Each domain is guaranteed a minimum quality of service and an admission control algorithm is used to determine whether a new QoS domain can be added without violating the QoS guarantees of existing domains. I/O requests from each QoS domain are maintained in separate FIFO queues and are serviced by a disk scheduler selects in accordance with the fair queuing scheduling algorithm of the invention which preserves the quality of service guarantees. An I/O request is maintained at the head of the corresponding domain queue while it is being serviced and is removed only after service completion.
According to the invention, the scheduling algorithm associates a start tag, Si, and a finish tag, Fi, with each domain queue i which is an element of the set of domains D. Initially, Si and Fi are both zero. As requests are added to a queue and subsequently serviced, the start and finish tags are updated as to reflect the estimated time required to service the request at the head of the queue with regard for the size of the input or output associated with the request and the proportion of disk bandwidth assigned to the particular domain. When the disk scheduler is ready to service a new request, the request is selected from the queue for the domain with the smallest finish tag among all busy domains, i.e., those domains which have I/O requests either waiting in the queue or being serviced. In this implementation, a domain can be safely deleted, freeing up the fraction of disk resource assigned to it, when the start tags for all of the other busy domains greater than or equal to the finish tag for the domain to be deleted.